1. Field of the Invention
The present invention relates generally to digital image processing and, more particularly, to wavelet-based compression of digital images.
2. Description of the Background Art
Today, digital imaging, particularly in the form of digital cameras, is a prevalent reality that affords a new way to capture photos using a solid-state image sensor instead of traditional film. A digital camera functions by recording incoming light on some sort of sensing mechanisms and then processes that information (basically, through analog-to-digital conversion) to create a memory image of the target picture. A digital camera's biggest advantage is that it creates images digitally thus making it easy to transfer images between all kinds of devices and applications. For instance, one can easily insert digital images into word processing documents, send them by e-mail to friends, or post them on a Web site where anyone in the world can see them. Additionally, one can use photo-editing software to manipulate digital images to improve or alter them. For example, one can crop them, remove red-eye, change colors or contrast, and even add and delete elements. Digital cameras also provide immediate access to one's images, thus avoiding the hassle and delay of film processing. All told, digital photography is becoming increasingly popular because of the flexibility it gives the user when he or she wants to use or distribute an image.
In order to generate an image of quality that is roughly comparable to a conventional photograph, a substantial amount of information must be captured and processed. For example, a low-resolution 640×480 image has 307,200 pixels. If each pixel uses 24 bits (3 bytes) for true color, a single image takes up about a megabyte of storage space. As the resolution increases, so does the image's file size. At a resolution of 1024×768, each 24-bit picture takes up 2.5 megabytes. Because of the large size of this information, digital cameras usually do not store a picture in its raw digital format but, instead, apply compression technique to the image so that it can be stored in a standard compressed image format, such as JPEG (Joint Photographic Experts Group). Compressing images allows the user to save more images on the camera's “digital film,” such as flash memory (available in a variety of specific formats) or other facsimile of film. It also allows the user to download and display those images more quickly.
Wavelet-based compression is the newest compression technology available on the consumer market. Wavelet technology enables digital images and video to be compressed by removing all obvious redundancy and using only the areas, which can be perceived, by the human eye primarily edges and shading changes which are generally represented by high frequencies. Wavelet technology filters the entire field or each frame at as a single entity. This approach results in smother images, as opposed to traditional JPEG style processing that may yield blocky images due to its block oriented processing. As a result, the technique provides a significant advantage for still images over the more traditional DCT-based methods that are used in the JPEG (baseline) industry standard. All told, wavelet-based methods offer the advantage of a better trade-off between complexity, compression, and quality. Accordingly, wavelet-based techniques are expanding in the field of still image and video compression at an ever-increasing rate.
The basic concept behind wavelets is that, rather than performing a tiling approach (i.e., breaking an image down into small segments), filters (and sub-band coding) are applied over the entirety of an image. This is illustrated in FIG. 1. First, a high pass filter and low pass filter are applied in parallel to separate the image, such that two results are generated one being the high-pass filtered results and low-pass filtered results, as shown at (a). Using Nyquist sampling theory, as the resultant images have reduced bandwidth, such that only half the amount of data is required for complete frequency representation, and thus the image can be sub-sampled by a factor of two with no information loss in the direction of filtering. This sub-sampling is simply done by removing every other resultant sample. This is done to both the high-pass and low pass results, such that the resultant data size is the same as the original image size. This approach is performed first in one direction either horizontal or vertical and then repeated in the other direction in a manner to produce four quadrants: first along an image's horizontal axis to produce high-pass and low-pass filtered halves, then repeating along an image's vertical access to produce high-pass and low-pass filtered quadrants, as shown at (b). Here, the upper left quadrant (Q1) represents low-pass horizontal and vertical image data. The upper right quadrant (Q2) represents high-pass horizontal and low-pass vertical image data. The lower left quadrant (Q3) represents low-pass horizontal and high-pass vertical image data. The lower right quadrant (Q4) represents high-pass horizontal and vertical image data. This process can be repeated at multiple levels, as shown at (c)-(e), by repeating the process on each resultant Q1 result each being a quarter the size of the previous level. This may continue until the resultant Q1 block is too small to continue further, yielding best compression.
Further description of the wavelet-based compression may be found, for instance, in the technical and trade literature. See e.g., Pigeon, S., Image Compression with Wavelets, Dr. Dobb's Journal, August 1999, pp. 111-115. The disclosure of the foregoing is hereby incorporated by reference, for all purposes.
Historically, wavelet processing has been implemented in software. In user-operated imaging devices, however, responsiveness to users is paramount. Therefore, there is great interest in finding a wavelet-based compression technique that is optimized for a given hardware environment. A particular problem arises when attempting to do hardware-based wavelet processing due to existing memory architecture, however. In particular, applying vertical filters using existing memory architecture is problematic.
Current memory architecture in widespread use (e.g., synchronous DRAMs—SDRAMs) is optimized for sequential data access in a horizontal manner, such as page-based or row-based access. For example, in the SDRAM memory commonly employed in PCs, horizontal access may be achieved on the order of 7-10 nanoseconds. This speed results from a pre-fetch pipelining mechanism, which is optimized for fetching the next data element (e.g., machine word) in a given row (“page”). Vertical access (e.g., accessing a pixel value below), in contrast, requires around 120 nanoseconds, a ten-fold increase in access cost. This increased cost results from the time-intensive task of switching to another row of memory cells. Here, the underlying memory access mechanism must be reconfigured to switch to the next memory page 2 to access the next group of bits.
One approach to mitigating the above limitation of current memory architecture is to employ alternative memory architecture—that is, forego use of RAM that is page oriented. One such example is static RAM (SRAM). Unfortunately, that approach has distinct disadvantages in terms of greatly increased cost, power requirements, and larger chip size. It is instead advantageous to find a solution that may be implemented using less-costly page-based memory architecture, if such a solution is possible.
All told, in a hardware-implemented wavelet processing approach, memory access becomes a limiting factor to a cost-effective solution. Therefore, there is great interest in finding a hardware-implemented wavelet-based compression solution that may be implemented in less-costly, page-based memory architecture (e.g., SDRAM), and do so in a manner that overcomes the inherent speed disadvantage encountered due to the horizontal-optimized access strategy employed by page-based memory architectures.